8.6. Tris¶
On décrit les algorithmes au programmme permettant de trier un tableau de valeurs numériques.
8.6.1. Tri par insertion¶
Le principe est très simple : c’est l’algorithme qu’utilise naturellement l’être humain pour trier des objets comme par exemple des cartes à jouer.
On procède en plusieurs étapes. On suppose qu’à l’étape \(i\), les éléments d’indice \(0\) à \(i-1\) du tableau sont déjà triés et on insère alors l’élément d’indice \(i\) à sa place parmi les éléments précédents.
Un dessin vaut probablement mieux qu’un long discours.
On peut alors proposer la fonction Python suivante.
In [1]: def tri_insertion(tab):
...: for i in range(1,len(tab)):
...: val = tab[i]
...: pos = i
...: while pos > 0 and tab[pos - 1] > val:
...: tab[pos] = tab[pos-1]
...: pos -= 1
...: tab[pos] = val
...:
On vérifie qu’elle fonctionne bien sur quelques tableaux choisis aléatoirement.
In [2]: from numpy.random import randint
In [3]: tab = randint(100, size=20)
In [4]: tab
Out[4]:
array([68, 16, 6, 36, 5, 36, 30, 6, 91, 65, 67, 17, 12, 34, 5, 53, 76,
97, 71, 61])
In [5]: tri_insertion(tab)
In [6]: tab
Out[6]:
array([ 5, 5, 6, 6, 12, 16, 17, 30, 34, 36, 36, 53, 61, 65, 67, 68, 71,
76, 91, 97])
À faire
preuve de l’algorithme + complexité
8.6.2. Tri rapide¶
Le tri rapide est une application du principe diviser pour régner. Il consiste
à choisir un élément du tableau à trier comme pivot ;
à séparer le tableau à trier en deux sous-tableaux contenant respectivement les éléments inférieurs et supérieurs au pivot ;
et à répéter le processus sur les deux sous-tableaux.
Comme tout algorithme du type diviser pour régner, le tri rapide se prête bien à une implémentation récursive 1.
In [7]: from numpy.random import choice
In [8]: def tri_rapide(tab):
...: if len(tab) == 0:
...: return []
...: pivot = choice(tab) # Choix aléatoire d'un élément comme pivot
...: t1, t2, t3 = [], [], []
...: for x in tab:
...: if x < pivot:
...: t1.append(x)
...: elif x > pivot:
...: t2.append(x)
...: else:
...: t3.append(x)
...: return tri_rapide(t1) + t3 + tri_rapide(t2)
...:
In [9]: from numpy.random import randint
In [10]: tab = randint(100, size=10)
In [11]: tab
Out[11]: array([49, 45, 79, 95, 48, 52, 44, 13, 29, 82])
In [12]: tri_rapide(tab)
Out[12]: [13, 29, 44, 45, 48, 49, 52, 79, 82, 95]
L’algorithme précédent crée une nouvelle liste à chaque appel de la fonction tri_rapide. D’un point de vue de l’utilisation de la mémoire, on peut préférer effectuer un tri en place : on modifie le tableau au cours de l’algorithme de tri.
In [13]: def partition(tab, g, d, p):
....: j = g
....: tab[p], tab[d] = tab[d], tab[p]
....: for i in range(g, d):
....: if tab[i] <= tab[d]:
....: tab[i], tab[j] = tab[j], tab[i]
....: j += 1
....: tab[d], tab[j] = tab[j], tab[d]
....: return j
....:
In [14]: def tri_rapide(tab, g=0, d=None):
....: if d == None:
....: d = len(tab) - 1
....: if g < d:
....: p = randint(g, d + 1)
....: pp = partition(tab, g, d, p)
....: tri_rapide(tab, g, pp - 1)
....: tri_rapide(tab, pp + 1, d)
....:
In [15]: tab = randint(100, size=10)
In [16]: tab
Out[16]: array([23, 7, 17, 59, 95, 35, 11, 79, 68, 52])
In [17]: tri_rapide(tab)
In [18]: tab
Out[18]: array([ 7, 11, 17, 23, 35, 52, 59, 68, 79, 95])
8.6.3. Tri par fusion¶
Le tri par fusion est également une application du principe diviser pour régner. Il consiste
à séparer la liste à trier en deux-sous listes si elle contient plus d’un élément ;
appliquer l’algorithme de tri aux deux sous-listes ;
fusionner les deux sous-listes triées en une liste triée.
L’algorithme de tri par fusion est de nature récursive par définition.
In [19]: def tri_fusion(tab):
....: if len(tab) < 2:
....: return tab
....: else:
....: m = len(tab)//2
....: return fusion(tri_fusion(tab[:m]), tri_fusion(tab[m:]))
....:
Le principe de fusion de deux listes triées en une liste triée est très simple :
on compare les deux premiers éléments de chacune des listes ;
on déplace le plus petit d’entre eux de la liste auquel il appartient vers la fin de la liste à renvoyer ;
on répète le processus jusqu’à ce qu’une des deux listes soient vides ;
on ajoute l’intégralité de l’autre liste à la fin de la liste à renvoyer.
In [20]: def fusion(t1, t2):
....: t = []
....: while t1 and t2:
....: if t1[0] < t2[0]:
....: t.append(t1.pop(0))
....: else:
....: t.append(t2.pop(0))
....: if t1:
....: t.extend(t1)
....: else:
....: t.extend(t2)
....: return t
....:
In [21]: from numpy.random import randint
In [22]: tab = list(randint(100, size=20))
In [23]: tab
Out[23]: [96, 71, 40, 26, 54, 22, 58, 7, 26, 30, 48, 28, 14, 13, 29, 60, 80, 1, 86, 21]
In [24]: tri_fusion(tab)
Out[24]: [1, 7, 13, 14, 21, 22, 26, 26, 28, 29, 30, 40, 48, 54, 58, 60, 71, 80, 86, 96]
On peut également donner une implémentation récursive de l’algorithme de fusion.
In [25]: def fusion(t1, t2):
....: if not t1:
....: return t2
....: if not t2:
....: return t1
....: if t1[0] < t2[0]:
....: return [t1[0]] + fusion(t1[1:], t2)
....: else:
....: return [t2[0]] + fusion(t1, t2[1:])
....:
In [26]: from numpy.random import randint
In [27]: tab = list(randint(100, size=10))
In [28]: tab
Out[28]: [53, 66, 84, 35, 50, 33, 24, 94, 6, 52]
In [29]: tri_fusion(tab)
Out[29]: [6, 24, 33, 35, 50, 52, 53, 66, 84, 94]
- 1
On peut également proposer une implémentation tirant partie des spécificités de Python (listes en compréhension).
In [30]: from numpy.random import choice In [31]: def tri_rapide(tab): ....: if len(tab) == 0: ....: return [] ....: pivot = choice(tab) ....: return tri_rapide([x for x in tab if x < pivot]) +\ ....: [x for x in tab if x == pivot] +\ ....: tri_rapide([x for x in tab if x > pivot]) ....:
In [32]: from numpy.random import randint In [33]: tab = randint(100, size=10) In [34]: tab Out[34]: array([79, 63, 14, 36, 45, 37, 83, 10, 37, 53]) In [35]: tri_rapide(tab) Out[35]: [10, 14, 36, 37, 37, 45, 53, 63, 79, 83]